package com.lintcode.solution;

import java.util.ArrayList;
import java.util.List;

public class Solution_35 {
    public static void main(String[] agrs) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        Solution_35 solution = new Solution_35();
        
        ListNode node = solution.reverse(head);
        ListNode temp = node;
        
        while (temp != null) {
            System.out.println(temp.val);
            temp = temp.next;
        }
    }
    
    public ListNode reverse(ListNode head) {
        if (head == null) {
            return null;
        }
        List<ListNode> list = new ArrayList<>();
        reverse(head, list);
        ListNode listNode = null, temp = null;
        for (int i = list.size() - 1; i >= 0; i--) {
            if (i == (list.size() - 1)) {
                listNode = temp = new ListNode(list.get(i).val);
            } else {
                if (temp != null) {
                    temp.next = list.get(i);
                    temp = temp.next;
                }
            }
        }
        return listNode;
    }
    
    public void reverse(ListNode head, List<ListNode> list) {
        if (head == null) {
            return;
        }
        list.add(new ListNode(head.val));
        reverse(head.next, list);
    }
}
